package leetcode_day._2021._202105._1120;

import java.util.*;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/5/18 21:57
 * 形成两个异或相等数组的三元组数目
 * 算法：前缀和
 * 在 [i, k] 中找到一个数字 j，使得 arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1] = arr[j] ^ ... ^ arr[k]
 * 由于相同数异或为 0 得 arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1] ^ arr[j] ^ ... ^ arr[k] = 0
 * 使用前缀异或表示：pre[j] ^ pre[i] == pre[k + 1] ^ pre[j] ===> pre[i] = pre[k + 1]
 * 只要 [i, k] 之间满足了 pre[i] = pre[k + 1] , 无论 j 取何值都成立
 */
public class _18_1442 {
    public static void main(String[] args) {
        System.out.println(new _18_1442().countTriplets_perfect(new int[]{2, 3, 1, 6, 7}));
    }

    public int countTriplets(int[] arr) {
        int[] pre = new int[arr.length + 1];
        for (int i = 1; i < pre.length; i++) pre[i] = pre[i - 1] ^ arr[i - 1];
        System.out.println(Arrays.toString(pre));
        int ans = 0;
        for (int i = 0; i < arr.length; i++)
            for (int j = i + 1; j < arr.length; j++)
                for (int k = j; k < arr.length; k++) {
                    int a = pre[j] ^ pre[i];
                    int b = pre[k + 1] ^ pre[j];
                    if (a == b) ++ans;
                }
        return ans;
    }

    public int countTriplets_perfect(int[] arr) {
        int ans = 0, pre = 0;
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int k = 0; k <= arr.length; k++) {
            if (k != 0) pre ^= arr[k - 1];
            List<Integer> list = map.getOrDefault(pre, new ArrayList<>());
            for (int idx : list) {
                ans += k - 1 - idx;
            }
            list.add(k);
            map.put(pre, list);
        }
        return ans;
    }
}
